// Copyright 2014 The Chromium Authors. All rights reserved.
// Use of this source code is governed by a BSD-style license that can be
// found in the LICENSE file.

#include "media/cast/sender/external_video_encoder.h"

#include <cmath>
#include <utility>

#include "base/bind.h"
#include "base/command_line.h"
#include "base/debug/crash_logging.h"
#include "base/debug/dump_without_crashing.h"
#include "base/format_macros.h"
#include "base/logging.h"
#include "base/macros.h"
#include "base/memory/shared_memory.h"
#include "base/message_loop/message_loop.h"
#include "base/metrics/histogram_macros.h"
#include "base/strings/string_number_conversions.h"
#include "base/strings/string_util.h"
#include "base/strings/stringprintf.h"
#include "build/build_config.h"
#include "media/base/bind_to_current_loop.h"
#include "media/base/media_switches.h"
#include "media/base/video_frame.h"
#include "media/base/video_types.h"
#include "media/base/video_util.h"
#include "media/cast/cast_config.h"
#include "media/cast/common/rtp_time.h"
#include "media/cast/logging/logging_defines.h"
#include "media/cast/net/cast_transport_config.h"
#include "media/cast/sender/vp8_quantizer_parser.h"
#include "media/filters/h264_parser.h"

namespace {

enum { MAX_H264_QUANTIZER = 51 };

// Number of buffers for encoded bit stream.
constexpr size_t kOutputBufferCount = 3;

// Maximum number of extra input buffers for encoder. The input buffers are only
// used when copy is needed to match the required coded size.
constexpr size_t kExtraInputBufferCount = 2;

// This value is used to calculate the encoder utilization. The encoder is
// assumed to be in full usage when the number of frames in progress reaches it.
constexpr int kBacklogRedlineThreshold = 4;

} // namespace

namespace media {
namespace cast {

    // Container for the associated data of a video frame being processed.
    struct InProgressFrameEncode {
        // The source content to encode.
        const scoped_refptr<VideoFrame> video_frame;

        // The reference time for this frame.
        const base::TimeTicks reference_time;

        // The callback to run when the result is ready.
        const VideoEncoder::FrameEncodedCallback frame_encoded_callback;

        // The target encode bit rate.
        const int target_bit_rate;

        // The real-world encode start time.  This is used to compute the encoded
        // frame's |encoder_utilization| and so it uses the real-world clock instead
        // of the CastEnvironment clock, the latter of which might be simulated.
        const base::TimeTicks start_time;

        InProgressFrameEncode(const scoped_refptr<VideoFrame>& v_frame,
            base::TimeTicks r_time,
            VideoEncoder::FrameEncodedCallback callback,
            int bit_rate)
            : video_frame(v_frame)
            , reference_time(r_time)
            , frame_encoded_callback(callback)
            , target_bit_rate(bit_rate)
            , start_time(base::TimeTicks::Now())
        {
        }
    };

    // Owns a VideoEncoderAccelerator instance and provides the necessary adapters
    // to encode media::VideoFrames and emit media::cast::EncodedFrames.  All
    // methods must be called on the thread associated with the given
    // SingleThreadTaskRunner, except for the task_runner() accessor.
    class ExternalVideoEncoder::VEAClientImpl
        : public VideoEncodeAccelerator::Client,
          public base::RefCountedThreadSafe<VEAClientImpl> {
    public:
        VEAClientImpl(
            const scoped_refptr<CastEnvironment>& cast_environment,
            const scoped_refptr<base::SingleThreadTaskRunner>& encoder_task_runner,
            std::unique_ptr<media::VideoEncodeAccelerator> vea,
            double max_frame_rate,
            const StatusChangeCallback& status_change_cb,
            const CreateVideoEncodeMemoryCallback& create_video_encode_memory_cb)
            : cast_environment_(cast_environment)
            , task_runner_(encoder_task_runner)
            , max_frame_rate_(max_frame_rate)
            , status_change_cb_(status_change_cb)
            , create_video_encode_memory_cb_(create_video_encode_memory_cb)
            , video_encode_accelerator_(std::move(vea))
            , encoder_active_(false)
            , next_frame_id_(FrameId::first())
            , key_frame_encountered_(false)
            , codec_profile_(media::VIDEO_CODEC_PROFILE_UNKNOWN)
            , key_frame_quantizer_parsable_(false)
            , requested_bit_rate_(-1)
            , has_seen_zero_length_encoded_frame_(false)
            , max_allowed_input_buffers_(0)
            , allocate_input_buffer_in_progress_(false)
        {
        }

        base::SingleThreadTaskRunner* task_runner() const
        {
            return task_runner_.get();
        }

        void Initialize(const gfx::Size& frame_size,
            VideoCodecProfile codec_profile,
            int start_bit_rate,
            FrameId first_frame_id)
        {
            DCHECK(task_runner_->RunsTasksOnCurrentThread());

            requested_bit_rate_ = start_bit_rate;
            encoder_active_ = video_encode_accelerator_->Initialize(
                media::PIXEL_FORMAT_I420, frame_size, codec_profile, start_bit_rate,
                this);
            next_frame_id_ = first_frame_id;
            codec_profile_ = codec_profile;

            UMA_HISTOGRAM_BOOLEAN("Cast.Sender.VideoEncodeAcceleratorInitializeSuccess",
                encoder_active_);

            cast_environment_->PostTask(
                CastEnvironment::MAIN,
                FROM_HERE,
                base::Bind(status_change_cb_,
                    encoder_active_ ? STATUS_INITIALIZED : STATUS_CODEC_INIT_FAILED));
        }

        void SetBitRate(int bit_rate)
        {
            DCHECK(task_runner_->RunsTasksOnCurrentThread());

            requested_bit_rate_ = bit_rate;
            video_encode_accelerator_->RequestEncodingParametersChange(
                bit_rate, static_cast<uint32_t>(max_frame_rate_ + 0.5));
        }

        // The destruction call back of the copied video frame to free its use of
        // the input buffer.
        void ReturnInputBufferToPool(int index)
        {
            DCHECK(task_runner_->RunsTasksOnCurrentThread());
            DCHECK_GE(index, 0);
            DCHECK_LT(index, static_cast<int>(input_buffers_.size()));
            free_input_buffer_index_.push_back(index);
        }

        void EncodeVideoFrame(
            const scoped_refptr<media::VideoFrame>& video_frame,
            const base::TimeTicks& reference_time,
            bool key_frame_requested,
            const VideoEncoder::FrameEncodedCallback& frame_encoded_callback)
        {
            DCHECK(task_runner_->RunsTasksOnCurrentThread());

            if (!encoder_active_)
                return;

            in_progress_frame_encodes_.push_back(InProgressFrameEncode(
                video_frame, reference_time, frame_encoded_callback,
                requested_bit_rate_));

            scoped_refptr<media::VideoFrame> frame = video_frame;
            if (video_frame->coded_size() != frame_coded_size_) {
                DCHECK_GE(frame_coded_size_.width(), video_frame->visible_rect().width());
                DCHECK_GE(frame_coded_size_.height(),
                    video_frame->visible_rect().height());

                if (free_input_buffer_index_.empty()) {
                    if (!allocate_input_buffer_in_progress_ && input_buffers_.size() < max_allowed_input_buffers_) {
                        allocate_input_buffer_in_progress_ = true;
                        create_video_encode_memory_cb_.Run(
                            media::VideoFrame::AllocationSize(media::PIXEL_FORMAT_I420,
                                frame_coded_size_),
                            base::Bind(&VEAClientImpl::OnCreateInputSharedMemory, this));
                    }
                    ExitEncodingWithErrors();
                    return;
                }

                int index = free_input_buffer_index_.back();
                base::SharedMemory* input_buffer = input_buffers_[index].get();
                frame = VideoFrame::WrapExternalSharedMemory(
                    video_frame->format(), frame_coded_size_, video_frame->visible_rect(),
                    video_frame->visible_rect().size(),
                    static_cast<uint8_t*>(input_buffer->memory()),
                    input_buffer->mapped_size(), input_buffer->handle(), 0,
                    video_frame->timestamp());
                if (!frame || !media::I420CopyWithPadding(*video_frame, frame.get())) {
                    LOG(DFATAL) << "Error: ExternalVideoEncoder: copy failed.";
                    ExitEncodingWithErrors();
                    return;
                }

                frame->AddDestructionObserver(media::BindToCurrentLoop(base::Bind(
                    &ExternalVideoEncoder::VEAClientImpl::ReturnInputBufferToPool, this,
                    index)));
                free_input_buffer_index_.pop_back();
            }

            // BitstreamBufferReady will be called once the encoder is done.
            video_encode_accelerator_->Encode(frame, key_frame_requested);
        }

    protected:
        void NotifyError(VideoEncodeAccelerator::Error error) final
        {
            DCHECK(task_runner_->RunsTasksOnCurrentThread());

            DCHECK(error != VideoEncodeAccelerator::kInvalidArgumentError && error != VideoEncodeAccelerator::kIllegalStateError);

            encoder_active_ = false;

            cast_environment_->PostTask(
                CastEnvironment::MAIN,
                FROM_HERE,
                base::Bind(status_change_cb_, STATUS_CODEC_RUNTIME_ERROR));

            // TODO(miu): Force-flush all |in_progress_frame_encodes_| immediately so
            // pending frames do not become stuck, freezing VideoSender.
        }

        // Called to allocate the input and output buffers.
        void RequireBitstreamBuffers(unsigned int input_count,
            const gfx::Size& input_coded_size,
            size_t output_buffer_size) final
        {
            DCHECK(task_runner_->RunsTasksOnCurrentThread());

            frame_coded_size_ = input_coded_size;

            max_allowed_input_buffers_ = input_count + kExtraInputBufferCount;

            for (size_t j = 0; j < kOutputBufferCount; ++j) {
                create_video_encode_memory_cb_.Run(
                    output_buffer_size,
                    base::Bind(&VEAClientImpl::OnCreateSharedMemory, this));
            }
        }

        // Encoder has encoded a frame and it's available in one of the output
        // buffers.  Package the result in a media::cast::EncodedFrame and post it
        // to the Cast MAIN thread via the supplied callback.
        void BitstreamBufferReady(int32_t bitstream_buffer_id,
            size_t payload_size,
            bool key_frame,
            base::TimeDelta /* timestamp */) final
        {
            DCHECK(task_runner_->RunsTasksOnCurrentThread());
            if (bitstream_buffer_id < 0 || bitstream_buffer_id >= static_cast<int32_t>(output_buffers_.size())) {
                NOTREACHED();
                VLOG(1) << "BitstreamBufferReady(): invalid bitstream_buffer_id="
                        << bitstream_buffer_id;
                NotifyError(media::VideoEncodeAccelerator::kPlatformFailureError);
                return;
            }
            base::SharedMemory* output_buffer = output_buffers_[bitstream_buffer_id].get();
            if (payload_size > output_buffer->mapped_size()) {
                NOTREACHED();
                VLOG(1) << "BitstreamBufferReady(): invalid payload_size = "
                        << payload_size;
                NotifyError(media::VideoEncodeAccelerator::kPlatformFailureError);
                return;
            }
            if (key_frame)
                key_frame_encountered_ = true;
            if (!key_frame_encountered_) {
                // Do not send video until we have encountered the first key frame.
                // Save the bitstream buffer in |stream_header_| to be sent later along
                // with the first key frame.
                //
                // TODO(miu): Should |stream_header_| be an std::ostringstream for
                // performance reasons?
                stream_header_.append(static_cast<const char*>(output_buffer->memory()),
                    payload_size);
            } else if (!in_progress_frame_encodes_.empty()) {
                const InProgressFrameEncode& request = in_progress_frame_encodes_.front();

                std::unique_ptr<SenderEncodedFrame> encoded_frame(
                    new SenderEncodedFrame());
                encoded_frame->dependency = key_frame ? EncodedFrame::KEY : EncodedFrame::DEPENDENT;
                encoded_frame->frame_id = next_frame_id_++;
                if (key_frame)
                    encoded_frame->referenced_frame_id = encoded_frame->frame_id;
                else
                    encoded_frame->referenced_frame_id = encoded_frame->frame_id - 1;
                encoded_frame->rtp_timestamp = RtpTimeTicks::FromTimeDelta(
                    request.video_frame->timestamp(), kVideoFrequency);
                encoded_frame->reference_time = request.reference_time;
                if (!stream_header_.empty()) {
                    encoded_frame->data = stream_header_;
                    stream_header_.clear();
                }
                encoded_frame->data.append(
                    static_cast<const char*>(output_buffer->memory()), payload_size);

                // If FRAME_DURATION metadata was provided in the source VideoFrame,
                // compute the utilization metrics.
                base::TimeDelta frame_duration;
                if (request.video_frame->metadata()->GetTimeDelta(
                        media::VideoFrameMetadata::FRAME_DURATION, &frame_duration)
                    && frame_duration > base::TimeDelta()) {
                    // Compute encoder utilization in terms of the number of frames in
                    // backlog, including the current frame encode that is finishing
                    // here. This "backlog" model works as follows: First, assume that all
                    // frames utilize the encoder by the same amount. This is actually a
                    // false assumption, but it still works well because any frame that
                    // takes longer to encode will naturally cause the backlog to
                    // increase, and this will result in a higher computed utilization for
                    // the offending frame. If the backlog continues to increase, because
                    // the following frames are also taking too long to encode, the
                    // computed utilization for each successive frame will be higher. At
                    // some point, upstream control logic will decide that the data volume
                    // must be reduced.
                    encoded_frame->encoder_utilization = static_cast<double>(in_progress_frame_encodes_.size()) / kBacklogRedlineThreshold;

                    const double actual_bit_rate = encoded_frame->data.size() * 8.0 / frame_duration.InSecondsF();
                    DCHECK_GT(request.target_bit_rate, 0);
                    const double bitrate_utilization = actual_bit_rate / request.target_bit_rate;
                    double quantizer = QuantizerEstimator::NO_RESULT;
                    // If the quantizer can be parsed from the key frame, try to parse
                    // the following delta frames as well.
                    // Otherwise, switch back to entropy estimation for the key frame
                    // and all the following delta frames.
                    if (key_frame || key_frame_quantizer_parsable_) {
                        if (codec_profile_ == media::VP8PROFILE_ANY) {
                            quantizer = ParseVp8HeaderQuantizer(
                                reinterpret_cast<const uint8_t*>(encoded_frame->data.data()),
                                encoded_frame->data.size());
                        } else if (codec_profile_ == media::H264PROFILE_MAIN) {
                            quantizer = GetH264FrameQuantizer(
                                reinterpret_cast<const uint8_t*>(encoded_frame->data.data()),
                                encoded_frame->data.size());
                        } else {
                            NOTIMPLEMENTED();
                        }
                        if (quantizer < 0) {
                            LOG(ERROR) << "Unable to parse quantizer from encoded "
                                       << (key_frame ? "key" : "delta")
                                       << " frame, id=" << encoded_frame->frame_id;
                            if (key_frame) {
                                key_frame_quantizer_parsable_ = false;
                                quantizer = quantizer_estimator_.EstimateForKeyFrame(
                                    *request.video_frame);
                            }
                        } else {
                            if (key_frame) {
                                key_frame_quantizer_parsable_ = true;
                            }
                        }
                    } else {
                        quantizer = quantizer_estimator_.EstimateForDeltaFrame(*request.video_frame);
                    }
                    if (quantizer >= 0) {
                        const double max_quantizer = codec_profile_ == media::VP8PROFILE_ANY
                            ? static_cast<int>(QuantizerEstimator::MAX_VP8_QUANTIZER)
                            : static_cast<int>(MAX_H264_QUANTIZER);
                        encoded_frame->lossy_utilization = bitrate_utilization * (quantizer / max_quantizer);
                    }
                } else {
                    quantizer_estimator_.Reset();
                }

                // TODO(miu): Determine when/why encoding can produce zero-length data,
                // which causes crypto crashes.  http://crbug.com/519022
                if (!has_seen_zero_length_encoded_frame_ && encoded_frame->data.empty()) {
                    has_seen_zero_length_encoded_frame_ = true;

                    const char kZeroEncodeDetails[] = "zero-encode-details";
                    const std::string details = base::StringPrintf(
                        ("%c/%c,id=%" PRIu32 ",rtp=%" PRIu32 ",br=%d,q=%" PRIuS
                         ",act=%c,ref=%" PRIu32),
                        codec_profile_ == media::VP8PROFILE_ANY ? 'V' : 'H',
                        key_frame ? 'K' : 'D', encoded_frame->frame_id.lower_32_bits(),
                        encoded_frame->rtp_timestamp.lower_32_bits(),
                        request.target_bit_rate / 1000, in_progress_frame_encodes_.size(),
                        encoder_active_ ? 'Y' : 'N',
                        encoded_frame->referenced_frame_id.lower_32_bits() % 1000);
                    base::debug::SetCrashKeyValue(kZeroEncodeDetails, details);
                    // Please forward crash reports to http://crbug.com/519022:
                    base::debug::DumpWithoutCrashing();
                    base::debug::ClearCrashKey(kZeroEncodeDetails);
                }

                encoded_frame->encode_completion_time = cast_environment_->Clock()->NowTicks();
                cast_environment_->PostTask(
                    CastEnvironment::MAIN,
                    FROM_HERE,
                    base::Bind(request.frame_encoded_callback,
                        base::Passed(&encoded_frame)));

                in_progress_frame_encodes_.pop_front();
            } else {
                VLOG(1) << "BitstreamBufferReady(): no encoded frame data available";
            }

            // We need to re-add the output buffer to the encoder after we are done
            // with it.
            video_encode_accelerator_->UseOutputBitstreamBuffer(media::BitstreamBuffer(
                bitstream_buffer_id,
                output_buffers_[bitstream_buffer_id]->handle(),
                output_buffers_[bitstream_buffer_id]->mapped_size()));
        }

    private:
        friend class base::RefCountedThreadSafe<VEAClientImpl>;

        ~VEAClientImpl() final
        {
            // According to the media::VideoEncodeAccelerator interface, Destroy()
            // should be called instead of invoking its private destructor.
            task_runner_->PostTask(
                FROM_HERE,
                base::Bind(&media::VideoEncodeAccelerator::Destroy,
                    base::Unretained(video_encode_accelerator_.release())));
        }

        // Note: This method can be called on any thread.
        void OnCreateSharedMemory(std::unique_ptr<base::SharedMemory> memory)
        {
            task_runner_->PostTask(FROM_HERE,
                base::Bind(&VEAClientImpl::OnReceivedSharedMemory,
                    this,
                    base::Passed(&memory)));
        }

        void OnCreateInputSharedMemory(std::unique_ptr<base::SharedMemory> memory)
        {
            task_runner_->PostTask(
                FROM_HERE, base::Bind(&VEAClientImpl::OnReceivedInputSharedMemory, this, base::Passed(&memory)));
        }

        void OnReceivedSharedMemory(std::unique_ptr<base::SharedMemory> memory)
        {
            DCHECK(task_runner_->RunsTasksOnCurrentThread());

            output_buffers_.push_back(std::move(memory));

            // Wait until all requested buffers are received.
            if (output_buffers_.size() < kOutputBufferCount)
                return;

            // Immediately provide all output buffers to the VEA.
            for (size_t i = 0; i < output_buffers_.size(); ++i) {
                video_encode_accelerator_->UseOutputBitstreamBuffer(
                    media::BitstreamBuffer(static_cast<int32_t>(i),
                        output_buffers_[i]->handle(),
                        output_buffers_[i]->mapped_size()));
            }
        }

        void OnReceivedInputSharedMemory(std::unique_ptr<base::SharedMemory> memory)
        {
            DCHECK(task_runner_->RunsTasksOnCurrentThread());

            if (memory.get()) {
                input_buffers_.push_back(std::move(memory));
                free_input_buffer_index_.push_back(input_buffers_.size() - 1);
            }
            allocate_input_buffer_in_progress_ = false;
        }

        // This is called when copy errors occur in encoding process when there is
        // need to copy the VideoFrames to match the required coded size for encoder.
        void ExitEncodingWithErrors()
        {
            DCHECK(task_runner_->RunsTasksOnCurrentThread());

            std::unique_ptr<SenderEncodedFrame> no_result(nullptr);
            cast_environment_->PostTask(
                CastEnvironment::MAIN, FROM_HERE,
                base::Bind(in_progress_frame_encodes_.back().frame_encoded_callback,
                    base::Passed(&no_result)));
            in_progress_frame_encodes_.pop_back();
        }

        // Parse H264 SPS, PPS, and Slice header, and return the averaged frame
        // quantizer in the range of [0, 51], or -1 on parse error.
        double GetH264FrameQuantizer(const uint8_t* encoded_data, off_t size)
        {
            DCHECK(encoded_data);
            if (!size)
                return -1;
            h264_parser_.SetStream(encoded_data, size);
            double total_quantizer = 0;
            int num_slices = 0;

            while (true) {
                H264NALU nalu;
                H264Parser::Result res = h264_parser_.AdvanceToNextNALU(&nalu);
                if (res == H264Parser::kEOStream)
                    break;
                if (res != H264Parser::kOk)
                    return -1;
                switch (nalu.nal_unit_type) {
                case H264NALU::kIDRSlice:
                case H264NALU::kNonIDRSlice: {
                    H264SliceHeader slice_header;
                    if (h264_parser_.ParseSliceHeader(nalu, &slice_header) != H264Parser::kOk)
                        return -1;
                    const H264PPS* pps = h264_parser_.GetPPS(slice_header.pic_parameter_set_id);
                    if (!pps)
                        return -1;
                    ++num_slices;
                    int slice_quantizer = 26 + ((slice_header.IsSPSlice() || slice_header.IsSISlice()) ? pps->pic_init_qs_minus26 + slice_header.slice_qs_delta : pps->pic_init_qp_minus26 + slice_header.slice_qp_delta);
                    DCHECK_GE(slice_quantizer, 0);
                    DCHECK_LE(slice_quantizer, MAX_H264_QUANTIZER);
                    total_quantizer += slice_quantizer;
                    break;
                }
                case H264NALU::kSPS: {
                    int id;
                    if (h264_parser_.ParseSPS(&id) != H264Parser::kOk)
                        return -1;
                    break;
                }
                case H264NALU::kPPS: {
                    int id;
                    if (h264_parser_.ParsePPS(&id) != H264Parser::kOk)
                        return -1;
                    break;
                }
                default:
                    // Skip other NALUs.
                    break;
                }
            }
            return (num_slices == 0) ? -1 : (total_quantizer / num_slices);
        }

        const scoped_refptr<CastEnvironment> cast_environment_;
        const scoped_refptr<base::SingleThreadTaskRunner> task_runner_;
        const double max_frame_rate_;
        const StatusChangeCallback status_change_cb_; // Must be run on MAIN thread.
        const CreateVideoEncodeMemoryCallback create_video_encode_memory_cb_;
        std::unique_ptr<media::VideoEncodeAccelerator> video_encode_accelerator_;
        bool encoder_active_;
        FrameId next_frame_id_;
        bool key_frame_encountered_;
        std::string stream_header_;
        VideoCodecProfile codec_profile_;
        bool key_frame_quantizer_parsable_;
        H264Parser h264_parser_;

        // Shared memory buffers for output with the VideoAccelerator.
        std::vector<std::unique_ptr<base::SharedMemory>> output_buffers_;

        // Shared memory buffers for input video frames with the VideoAccelerator.
        // These buffers will be allocated only when copy is needed to match the
        // required coded size for encoder. They are allocated on-demand, up to
        // |max_allowed_input_buffers_|.
        std::vector<std::unique_ptr<base::SharedMemory>> input_buffers_;

        // Available input buffer index. These buffers are used in FILO order.
        std::vector<int> free_input_buffer_index_;

        // FIFO list.
        std::list<InProgressFrameEncode> in_progress_frame_encodes_;

        // The requested encode bit rate for the next frame.
        int requested_bit_rate_;

        // Used to compute utilization metrics for each frame.
        QuantizerEstimator quantizer_estimator_;

        // Set to true once a frame with zero-length encoded data has been
        // encountered.
        // TODO(miu): Remove after discovering cause.  http://crbug.com/519022
        bool has_seen_zero_length_encoded_frame_;

        // The coded size of the video frame required by Encoder. This size is
        // obtained from VEA through |RequireBitstreamBuffers()|.
        gfx::Size frame_coded_size_;

        // The maximum number of input buffers. These buffers are used to copy
        // VideoFrames in order to match the required coded size for encoder.
        size_t max_allowed_input_buffers_;

        // Set to true when the allocation of an input buffer is in progress, and
        // reset to false after the allocated buffer is received.
        bool allocate_input_buffer_in_progress_;

        DISALLOW_COPY_AND_ASSIGN(VEAClientImpl);
    };

    // static
    bool ExternalVideoEncoder::IsSupported(const FrameSenderConfig& video_config)
    {
        if (video_config.codec != CODEC_VIDEO_VP8 && video_config.codec != CODEC_VIDEO_H264)
            return false;

        // TODO(miu): "Layering hooks" are needed to be able to query outside of
        // libmedia, to determine whether the system provides a hardware encoder.  For
        // now, assume that this was already checked by this point.
        // http://crbug.com/454029
        return video_config.use_external_encoder;
    }

    ExternalVideoEncoder::ExternalVideoEncoder(
        const scoped_refptr<CastEnvironment>& cast_environment,
        const FrameSenderConfig& video_config,
        const gfx::Size& frame_size,
        FrameId first_frame_id,
        const StatusChangeCallback& status_change_cb,
        const CreateVideoEncodeAcceleratorCallback& create_vea_cb,
        const CreateVideoEncodeMemoryCallback& create_video_encode_memory_cb)
        : cast_environment_(cast_environment)
        , create_video_encode_memory_cb_(create_video_encode_memory_cb)
        , frame_size_(frame_size)
        , bit_rate_(video_config.start_bitrate)
        , key_frame_requested_(false)
        , weak_factory_(this)
    {
        DCHECK(cast_environment_->CurrentlyOn(CastEnvironment::MAIN));
        DCHECK_GT(video_config.max_frame_rate, 0);
        DCHECK(!frame_size_.IsEmpty());
        DCHECK(!status_change_cb.is_null());
        DCHECK(!create_vea_cb.is_null());
        DCHECK(!create_video_encode_memory_cb_.is_null());
        DCHECK_GT(bit_rate_, 0);

        create_vea_cb.Run(
            base::Bind(&ExternalVideoEncoder::OnCreateVideoEncodeAccelerator,
                weak_factory_.GetWeakPtr(),
                video_config,
                first_frame_id,
                status_change_cb));
    }

    ExternalVideoEncoder::~ExternalVideoEncoder()
    {
    }

    bool ExternalVideoEncoder::EncodeVideoFrame(
        const scoped_refptr<media::VideoFrame>& video_frame,
        const base::TimeTicks& reference_time,
        const FrameEncodedCallback& frame_encoded_callback)
    {
        DCHECK(cast_environment_->CurrentlyOn(CastEnvironment::MAIN));
        DCHECK(!frame_encoded_callback.is_null());

        if (!client_ || video_frame->visible_rect().size() != frame_size_)
            return false;

        client_->task_runner()->PostTask(FROM_HERE,
            base::Bind(&VEAClientImpl::EncodeVideoFrame,
                client_,
                video_frame,
                reference_time,
                key_frame_requested_,
                frame_encoded_callback));
        key_frame_requested_ = false;
        return true;
    }

    void ExternalVideoEncoder::SetBitRate(int new_bit_rate)
    {
        DCHECK(cast_environment_->CurrentlyOn(CastEnvironment::MAIN));
        DCHECK_GT(new_bit_rate, 0);

        bit_rate_ = new_bit_rate;
        if (!client_)
            return;
        client_->task_runner()->PostTask(
            FROM_HERE, base::Bind(&VEAClientImpl::SetBitRate, client_, bit_rate_));
    }

    void ExternalVideoEncoder::GenerateKeyFrame()
    {
        DCHECK(cast_environment_->CurrentlyOn(CastEnvironment::MAIN));
        key_frame_requested_ = true;
    }

    void ExternalVideoEncoder::OnCreateVideoEncodeAccelerator(
        const FrameSenderConfig& video_config,
        FrameId first_frame_id,
        const StatusChangeCallback& status_change_cb,
        scoped_refptr<base::SingleThreadTaskRunner> encoder_task_runner,
        std::unique_ptr<media::VideoEncodeAccelerator> vea)
    {
        DCHECK(cast_environment_->CurrentlyOn(CastEnvironment::MAIN));

        // The callback will be invoked with null pointers in the case where the
        // system does not support or lacks the resources to provide GPU-accelerated
        // video encoding.
        if (!encoder_task_runner || !vea) {
            cast_environment_->PostTask(
                CastEnvironment::MAIN,
                FROM_HERE,
                base::Bind(status_change_cb, STATUS_CODEC_INIT_FAILED));
            return;
        }

        VideoCodecProfile codec_profile;
        switch (video_config.codec) {
        case CODEC_VIDEO_VP8:
            codec_profile = media::VP8PROFILE_ANY;
            break;
        case CODEC_VIDEO_H264:
            codec_profile = media::H264PROFILE_MAIN;
            break;
        case CODEC_VIDEO_FAKE:
            NOTREACHED() << "Fake software video encoder cannot be external";
            // ...flow through to next case...
        default:
            cast_environment_->PostTask(
                CastEnvironment::MAIN,
                FROM_HERE,
                base::Bind(status_change_cb, STATUS_UNSUPPORTED_CODEC));
            return;
        }

        DCHECK(!client_);
        client_ = new VEAClientImpl(cast_environment_, encoder_task_runner,
            std::move(vea), video_config.max_frame_rate,
            status_change_cb, create_video_encode_memory_cb_);
        client_->task_runner()->PostTask(FROM_HERE,
            base::Bind(&VEAClientImpl::Initialize,
                client_,
                frame_size_,
                codec_profile,
                bit_rate_,
                first_frame_id));
    }

    SizeAdaptableExternalVideoEncoder::SizeAdaptableExternalVideoEncoder(
        const scoped_refptr<CastEnvironment>& cast_environment,
        const FrameSenderConfig& video_config,
        const StatusChangeCallback& status_change_cb,
        const CreateVideoEncodeAcceleratorCallback& create_vea_cb,
        const CreateVideoEncodeMemoryCallback& create_video_encode_memory_cb)
        : SizeAdaptableVideoEncoderBase(cast_environment,
            video_config,
            status_change_cb)
        , create_vea_cb_(create_vea_cb)
        , create_video_encode_memory_cb_(create_video_encode_memory_cb)
    {
    }

    SizeAdaptableExternalVideoEncoder::~SizeAdaptableExternalVideoEncoder() { }

    std::unique_ptr<VideoEncoder>
    SizeAdaptableExternalVideoEncoder::CreateEncoder()
    {
        return std::unique_ptr<VideoEncoder>(new ExternalVideoEncoder(
            cast_environment(), video_config(), frame_size(), next_frame_id(),
            CreateEncoderStatusChangeCallback(), create_vea_cb_,
            create_video_encode_memory_cb_));
    }

    QuantizerEstimator::QuantizerEstimator() { }

    QuantizerEstimator::~QuantizerEstimator() { }

    void QuantizerEstimator::Reset()
    {
        last_frame_pixel_buffer_.reset();
    }

    double QuantizerEstimator::EstimateForKeyFrame(const VideoFrame& frame)
    {
        if (!CanExamineFrame(frame))
            return NO_RESULT;

        // If the size of the frame is different from the last frame, allocate a new
        // buffer.  The buffer only needs to be a fraction of the size of the entire
        // frame, since the entropy analysis only examines a subset of each frame.
        const gfx::Size size = frame.visible_rect().size();
        const int rows_in_subset = std::max(1, size.height() * FRAME_SAMPLING_PERCENT / 100);
        if (last_frame_size_ != size || !last_frame_pixel_buffer_) {
            last_frame_pixel_buffer_.reset(new uint8_t[size.width() * rows_in_subset]);
            last_frame_size_ = size;
        }

        // Compute a histogram where each bucket represents the number of times two
        // neighboring pixels were different by a specific amount.  511 buckets are
        // needed, one for each integer in the range [-255,255].
        int histogram[511];
        memset(histogram, 0, sizeof(histogram));
        const int row_skip = size.height() / rows_in_subset;
        int y = 0;
        for (int i = 0; i < rows_in_subset; ++i, y += row_skip) {
            const uint8_t* const row_begin = frame.visible_data(VideoFrame::kYPlane) + y * frame.stride(VideoFrame::kYPlane);
            const uint8_t* const row_end = row_begin + size.width();
            int left_hand_pixel_value = static_cast<int>(*row_begin);
            for (const uint8_t* p = row_begin + 1; p < row_end; ++p) {
                const int right_hand_pixel_value = static_cast<int>(*p);
                const int difference = right_hand_pixel_value - left_hand_pixel_value;
                const int histogram_index = difference + 255;
                ++histogram[histogram_index];
                left_hand_pixel_value = right_hand_pixel_value; // For next iteration.
            }

            // Copy the row of pixels into the buffer.  This will be used when
            // generating histograms for future delta frames.
            memcpy(last_frame_pixel_buffer_.get() + i * size.width(),
                row_begin,
                size.width());
        }

        // Estimate a quantizer value depending on the difference data in the
        // histogram and return it.
        const int num_samples = (size.width() - 1) * rows_in_subset;
        return ToQuantizerEstimate(ComputeEntropyFromHistogram(
            histogram, arraysize(histogram), num_samples));
    }

    double QuantizerEstimator::EstimateForDeltaFrame(const VideoFrame& frame)
    {
        if (!CanExamineFrame(frame))
            return NO_RESULT;

        // If the size of the |frame| has changed, no difference can be examined.
        // In this case, process this frame as if it were a key frame.
        const gfx::Size size = frame.visible_rect().size();
        if (last_frame_size_ != size || !last_frame_pixel_buffer_)
            return EstimateForKeyFrame(frame);
        const int rows_in_subset = std::max(1, size.height() * FRAME_SAMPLING_PERCENT / 100);

        // Compute a histogram where each bucket represents the number of times the
        // same pixel in this frame versus the last frame was different by a specific
        // amount.  511 buckets are needed, one for each integer in the range
        // [-255,255].
        int histogram[511];
        memset(histogram, 0, sizeof(histogram));
        const int row_skip = size.height() / rows_in_subset;
        int y = 0;
        for (int i = 0; i < rows_in_subset; ++i, y += row_skip) {
            const uint8_t* const row_begin = frame.visible_data(VideoFrame::kYPlane) + y * frame.stride(VideoFrame::kYPlane);
            const uint8_t* const row_end = row_begin + size.width();
            uint8_t* const last_frame_row_begin = last_frame_pixel_buffer_.get() + i * size.width();
            for (const uint8_t *p = row_begin, *q = last_frame_row_begin; p < row_end;
                 ++p, ++q) {
                const int difference = static_cast<int>(*p) - static_cast<int>(*q);
                const int histogram_index = difference + 255;
                ++histogram[histogram_index];
            }

            // Copy the row of pixels into the buffer.  This will be used when
            // generating histograms for future delta frames.
            memcpy(last_frame_row_begin, row_begin, size.width());
        }

        // Estimate a quantizer value depending on the difference data in the
        // histogram and return it.
        const int num_samples = size.width() * rows_in_subset;
        return ToQuantizerEstimate(ComputeEntropyFromHistogram(
            histogram, arraysize(histogram), num_samples));
    }

    // static
    bool QuantizerEstimator::CanExamineFrame(const VideoFrame& frame)
    {
        DCHECK_EQ(8, VideoFrame::PlaneHorizontalBitsPerPixel(frame.format(), VideoFrame::kYPlane));
        return media::IsYuvPlanar(frame.format()) && !frame.visible_rect().IsEmpty();
    }

    // static
    double QuantizerEstimator::ComputeEntropyFromHistogram(const int* histogram,
        size_t num_buckets,
        int num_samples)
    {
#if defined(OS_ANDROID)
        // Android does not currently provide a log2() function in their C++ standard
        // library.  This is a substitute.
        const auto log2 = [](double num) -> double {
            return log(num) / 0.69314718055994528622676398299518041312694549560546875;
        };
#endif

        DCHECK_LT(0, num_samples);
        double entropy = 0.0;
        for (size_t i = 0; i < num_buckets; ++i) {
            const double probability = static_cast<double>(histogram[i]) / num_samples;
            if (probability > 0.0)
                entropy = entropy - probability * log2(probability);
        }
        return entropy;
    }

    // static
    double QuantizerEstimator::ToQuantizerEstimate(double shannon_entropy)
    {
        DCHECK_GE(shannon_entropy, 0.0);

        // This math is based on an analysis of data produced by running a wide range
        // of mirroring content in a Cast streaming session on a Chromebook Pixel
        // (2013 edition).  The output from the Pixel's built-in hardware encoder was
        // compared to an identically-configured software implementation (libvpx)
        // running alongside.  Based on an analysis of the data, the following linear
        // mapping seems to produce reasonable VP8 quantizer values from the
        // |shannon_entropy| values.
        //
        // TODO(miu): Confirm whether this model and value work well on other
        // platforms.
        const double kEntropyAtMaxQuantizer = 7.5;
        const double slope = (MAX_VP8_QUANTIZER - MIN_VP8_QUANTIZER) / kEntropyAtMaxQuantizer;
        const double quantizer = std::min<double>(
            MAX_VP8_QUANTIZER, MIN_VP8_QUANTIZER + slope * shannon_entropy);
        return quantizer;
    }

} //  namespace cast
} //  namespace media
